#include<iostream>
#include<vector>
using std::endl;
using std::cout;
using std::vector;
template <typename T, typename Compare = std::less<T>>
class HeapSort 
{ 
public:  
    HeapSort(T *arr, size_t size, Compare com);  
    void heapAdjust(size_t ,size_t ,Compare &com);  
    void sort(Compare &&com);  
    void print();
private:  
    vector<T> vec; 
};
template <typename T, typename Compare> 
void HeapSort<T,Compare>::print(){
    for(auto &ele :vec){
        cout<<ele <<" ";
    }
    cout<<endl;
}

template <typename T, typename Compare> 
HeapSort<T,Compare>::HeapSort(T *arr, size_t size, Compare com)
:vec(arr,arr+size)
{}
template <typename T, typename Compare> 
void HeapSort<T,Compare>::heapAdjust(size_t i ,size_t size ,Compare &com){
    size_t dad_idx = i;
    size_t son_idx = i*2 + 1;
    while(son_idx < size){
        if(son_idx+1 < size && com(vec[son_idx],vec[son_idx+1])){
            ++son_idx;
        }
        if(com(vec[dad_idx],vec[son_idx])){
            std::swap(vec[dad_idx],vec[son_idx]);
            dad_idx = son_idx;
            son_idx = dad_idx *2 + 1;
        }else{
            break;
        }
    }
}
template <typename T, typename Compare>
void HeapSort<T,Compare>::sort(Compare &&com){
    int N = vec.size();
    for(int i = N/2 - 1;i>=0;--i){
        heapAdjust(i,N,com);
    }
    std::swap(vec[0],vec[N-1]);
    for(int size = N-1;size > 1; --size){
        heapAdjust(0,size,com);
        std::swap(vec[0],vec[size-1]);
    }
}

void test() {
    srand(time(NULL));
    int *arr = (int *)malloc(sizeof(int) * 10);
    for(int i = 0; i <  10; i++ ) {
        arr[i] = rand() % 100;
    }
    for(int i = 0;i<10;i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    HeapSort<int> heap(arr,10,std::less<int>());
    heap.print();
    heap.sort(std::less<int>());
    heap.print();
}
int main(void){
    test();
}